# 51/100 图论-岛屿数量
# leetcode第200题: https://leetcode.cn/problems/number-of-islands/description/?envType=study-plan-v2&envId=top-100-liked
# Date: 2024/11/27
from leetcode import test


def numIslands(grid: list[list[str]]) -> int:
    m, n = len(grid), len(grid[0])

    if m == n == 1:
        return int(grid[0][0])

    visited = [[False] * n for _ in range(m)]

    def dfs(row: int, col: int):
        if not visited[row][col]:
            visited[row][col] = True
            if col < n - 1 and not visited[row][col + 1] and grid[row][col + 1] == "1":
                dfs(row, col + 1)  # 向右
            if row < m - 1 and not visited[row + 1][col] and grid[row + 1][col] == "1":
                dfs(row + 1, col)  # 向下
            if col > 0 and not visited[row][col - 1] and grid[row][col - 1] == "1":
                dfs(row, col - 1)  # 向左
            if row > 0 and not visited[row - 1][col] and grid[row - 1][col] == "1":
                dfs(row - 1, col)  # 向上

    res = 0
    for i in range(m):
        for j in range(n):
            if grid[i][j] == "1" and not visited[i][j]:
                dfs(i, j)
                res += 1

    return res


if __name__ == '__main__':
    grid = [
        ["1", "1", "1", "1", "0"],
        ["1", "1", "0", "1", "0"],
        ["1", "1", "0", "0", "0"],
        ["0", "0", "0", "0", "0"]
    ]

    grid1 = [
        ["1", "1", "0", "0", "0"],
        ["1", "1", "0", "0", "0"],
        ["0", "0", "1", "0", "0"],
        ["0", "0", "0", "1", "1"]
    ]

    grid2 = [["1", "1", "1"],
             ["0", "1", "0"],
             ["1", "1", "1"]]

    print(numIslands(grid))  # 1
    print(numIslands(grid1))  # 3
    print(numIslands(grid2))  # 1
